#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class TrieNode(dict):
    def __init__(self, is_word_end=False):
        self.is_word_end = False
        # self.parent = None      # TrieNode

    def add_child(self, c, set_true=False):
        if c not in self:
            self[c] = TrieNode()

        t = self[c]

        if set_true:
            t.is_word_end = True

        return t


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        cur_node = self.root

        word_len = len(word)
        for c in word:
            cur_node = cur_node.add_child(c)

        cur_node.is_word_end = True

    def _match(self, word, need_end=False):
        # proper: 是否需要结尾is_word_end是True
        cur_node = self.root

        for c in word:
            if c not in cur_node:
                return False

            cur_node = cur_node[c]

        if need_end:
            return cur_node.is_word_end
        else:
            return True

    def search(self, word):
        # print(self._match(word, need_end=True))
        return self._match(word, need_end=True)

    def startsWith(self, prefix):
        # print(self._match(prefix, need_end=False))
        return self._match(prefix, need_end=False)


def main():
    print("start main")
    s = Trie()
    s.insert('a')
    s.insert('ab')
    # s.insert('a')

    # ret = s.search('a')
    ret = s.search('ab')
    print(ret)

    ret = s.search('a')
    print(ret)

    ret = s.startsWith('a')
    print(ret)

    # print(s.root['a']['b']['c'].is_word_end)
    # print(s.root['a']['b'].is_word_end)
    # print(s.root['a'].is_word_end)

if __name__ == "__main__":
    main()
